import java.util.ArrayList;
import java.util.List;

public class findAnagrams {
    /**
     * 找到字符串中所有字母异位词，滑动窗口
     * @author ShakeJ
     * @date 2024/3/18
     */
    public static List<Integer> method(String s, String p){
        // 分别记录两个字符串的长度
        int n=s.length(), m=p.length();
        List<Integer> res=new ArrayList<>();
        if(n<m){
            return res;
        }

        int[] pcnt=new int[26];
        int[] scnt=new int[26];

        for(int i=0;i<m;i++){
            // 目标子串中的字符
            pcnt[p.charAt(i)-'a']++;
        }
        int left=0;
        for(int right = 0; right<n;right++){
            int curRight=s.charAt(right) - 'a'; //当前元素
            scnt[curRight]++; //对应位置
            while(scnt[curRight]>pcnt[curRight]){
                int curLeft=s.charAt(left)-'a';
                scnt[curLeft]--;
                left++;
            }
            if(right-left+1==m){
                res.add(left); //返回滑动窗口的起始位置
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";
        System.out.println(method(s,p));
    }
}
